package demo2;

/**
 * Created with IntelliJ IDEA
 * Description:
 * User:34398
 * Date:2024-03-31
 * Time:11:51
 */
class Node<T> {
    T data;
    Node<T> next;

    Node(T data) {
        this.data = data;
        this.next = null;
    }
}

public class LinkedListSortExample<T extends Comparable<T>> {

    Node<T> head;

    public LinkedListSortExample() {//构造方法
        head = null;
    }

    public void add(T data) {//增
        Node<T> newNode = new Node<>(data);
        if (head == null) {
            head = newNode;
        } else {
            newNode.next = head;
            head = newNode;
        }
    }

    public void display() {//打印
        Node<T> current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }

    public void sort() {//排序
        if (head == null) return;
        Node<T> pivot = head;
        Node<T> tail = pivot;
        head = null;
        while (tail != null) {
            Node<T> next = tail.next;
            add(tail.data);
            tail = next;
        }
        quickSort(head);
    }

    private void quickSort(Node<T> node) {
        if (node == null || node.next == null) return;
        Node<T> slow = node;
        Node<T> fast = node.next;
        T pivot = node.data;
        while (fast != null) {
            if (fast.data.compareTo(pivot) < 0) {
                slow = slow.next;
                T temp = slow.data;
                slow.data = fast.data;
                fast.data = temp;
            }
            fast = fast.next;
        }
        quickSort(node);
        quickSort(slow.next);
    }

    public static void main(String[] args) {
        LinkedListSortExample<Integer> list = new LinkedListSortExample<>();
        list.add(3);
        list.add(2);
        list.add(4);
        list.add(1);
        System.out.println("Before sorting:");
        list.display(); // 输出: 3 2 4 1
        list.sort();
        System.out.println("After sorting:");
        list.display(); // 输出排序后的链表: 1 2 3 4
    }
}